프로그래머스_괄호 변환
2022.01.27
문제
’(’ 와 ’)’ 로만 이루어진 문자열이 있을 경우, ’(’ 의 개수와 ’)’ 의 개수가 같다면 이를 균형잡힌 괄호 문자열
그리고 여기에 ’(‘와 ’)‘의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열
1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.
3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.
4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.
4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.
4-3. ')'를 다시 붙입니다.
4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.
4-5. 생성된 문자열을 반환합니다.
"균형잡힌 괄호 문자열" p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 "올바른 괄호 문자열"로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.접근 방법
- 먼저 u, v로 나눌 인덱스 위치를 구해야한다. u는
균형잡힌 괄호 문자열이고, 더 이상 분리할 수 없어야 하기 때문에가능한 최소의 길이가 되는 인덱스를 찾으면 된다.(일 때는++하고,)일 때는--하여 카운트 값이0이 되는 순간이균형잡힌 괄호 문자열이 되는 순간이다. - 해당 인덱스를 기준으로 u, v 문자열을 만든다.
-
u 문자열이
올바른 괄호 문자열인지 확인한다.(이면 스택에push하고,)이면pop하여 최종적으로 스택의 사이즈가 비었는지 확인하면 된다. 비어있다면 올바른 괄호 문자열이다.- 만약 올바른 괄호 문자열이라면, u 문자열을 정답에 추가하고, v 문자열을 재귀호출하여 1단계부터 다시 수행한다.
- 만약 올바르지 않은 괄호 문자열이라면,
- ( 문자를 추가
- v 문자열을 재귀호출하여 1단계부터 수행
- ) 문자 추가
- 맨앞과 맨뒤의 문자를 삭제한 u문자를 뒤집은 뒤에 정답의 끝에 추가한다.
정답 문자열(answer)은 반환하기 전까지 재귀적으로 반복하면서 새로운 문자열을 생성하기 때문에 String 으로 + 연산을 통해 더하는 방법이 아닌, StringBuilder를 사용하는 것이 좋다. StringBuilder는 가변성을 가지기 때문에 문자열의 추가, 삭제가 빈번하게 발생하는 경우 사용하면 속도와 메모리 측면에서 효과를 볼 수 있다.
소스 코드
import java.util.*;
class Solution {
public String solution(String p) {
return makeValidString(p);
}
private String makeValidString(String str) {
if (str.length() == 0) {
return "";
}
int splitIndex = getSplitIndex(str);
String left = str.substring(0, splitIndex);
String right = str.substring(splitIndex);
StringBuilder answer = new StringBuilder();
if (isValid(left)) {
answer.append(left)
.append(makeValidString(right));
} else {
answer.append('(')
.append(makeValidString(right))
.append(')')
.append(changeString(left.substring(1, left.length() - 1)));
}
return answer.toString();
}
private String changeString(String str) {
StringBuilder newString = new StringBuilder();
for (char ch : str.toCharArray()) {
if (ch == '(') {
newString.append(')');
} else {
newString.append('(');
}
}
return newString.toString();
}
private boolean isValid(String str) {
Stack<Character> stack = new Stack<>();
for (char ch : str.toCharArray()) {
if (ch == '(') {
stack.add(ch);
} else {
if (!stack.isEmpty()) {
stack.pop();
}
}
}
return stack.isEmpty();
}
private int getSplitIndex(String str) {
int count = 0;
for (int i=0; i<str.length(); i++) {
if (i>0 && count == 0) {
return i;
}
if (str.charAt(i) == '(') {
count++;
} else {
count--;
}
}
return str.length();
}
}